# coding: utf-8
# 快速排序实现

# 一行代码实现的简洁版本
quick_sort1 = lambda array: \
array if len(array) <= 1 \
else quick_sort1([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort1([item for item in array[1:] if item > array[0]])

#《算法导论》中的快排程序（原地排序）
def quick_sort2(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort2(array, l, q - 1)
        quick_sort2(array, q + 1, r)
 
def partition(array, l, r):
    # pivot
    x = array[r]
    # 指针i记录小于等于x的元素位置
    i = l - 1
    # rang(1,4)=[1,2,3] end取不到
    # 指针j进行遍历
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            # 交换i和j
            array[i], array[j] = array[j], array[i]
    # 把pivot放到正确的位置
    array[i + 1], array[r] = array[r], array[i+1]
    return i + 1

lst = [1,11,2,22,3,33,1,2,3]
lstLen = len(lst)

print("origin:",lst)

print("quick_sort1:", quick_sort1(lst))

quick_sort2(lst,0,lstLen-1)
print("quick_sort2:", lst)

